type TrieNode struct {
    children [26]*TrieNode
    word     string
}

func buildTrie(words []string) *TrieNode {
    root := &TrieNode{}
    for _, s := range words {
        curr := root
        for _, c := range s {
            index := c - 'a'
            if curr.children[index] == nil {
                curr.children[index] = &TrieNode{}
            }
            curr = curr.children[index]
        }
        curr.word = s
    }
    return root
}

func findWords(board [][]byte, words []string) []string {
    var dirs = [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    var m, n = len(board), len(board[0])
    var visited = make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }
    seen := map[string]bool{}

    var dfs func(int, int, *TrieNode)
    dfs = func(row int, col int, node *TrieNode) {
        if node.children[board[row][col] - 'a'] == nil {
            return
        }

        node = node.children[board[row][col] - 'a']
        if node.word != "" {
            seen[node.word] = true
            node.word = ""
        }

        visited[row][col] = true
        for _, dir := range dirs {
            var nextRow = row + dir[0]
            var nextCol = col + dir[1]
            if nextRow >= 0 && nextRow < m &&
                    nextCol >= 0 && nextCol < n &&
                    !visited[nextRow][nextCol] {
                dfs(nextRow, nextCol, node)
            }
        }
        visited[row][col] = false
    }

    root := buildTrie(words)
    for row := 0; row < m; row++ {
        for col := 0; col < n; col++ {
            dfs(row, col, root)
        }
    }

    ans := make([]string, 0, len(seen))
    for s := range seen {
        ans = append(ans, s)
    }
    return ans
}